package niuke.week3;

import java.util.Scanner;

/**
 现有n1+n2种面值的硬币，其中前n1种为普通币，可以取任意枚，
 后n2种为纪念币，每种最多只能取一枚，每种硬币有一个面值，问能用多少种方法拼出m的面值?


 第一行输入三个整数n1,n2,m        n1,n2<=1000 m<=100000
 第二行输入n1个整数表示普通币的面值
 第三行输入n2个整数表示纪念币的面值
 不同的硬币面值可能相同


 使用编号不同但面值相同的硬币算不同的拼法
 输出用多少种方法拼出m的面值，由于答案过大，对1e9 + 7取模

 */
public class CoinsTogether {
    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        int n1 = sc.nextInt();//  普通币\券
        int n2= sc.nextInt();//  纪念币
        int sum = sc.nextInt();

        int[] arr1 = new int[n1];//普通币\券
        int[] arr2 = new int[n2];//纪念币

        for(int i = 0; i < n1; i++){//普通币\券
            arr1[i] = sc.nextInt();
        }
        for(int i = 0; i < n2; i++){//纪念币
            arr2[i] = sc.nextInt();
        }


        /////////用券的   dp_i,j  【0.。。i】号券，搞定j元有多少种方式 ////////////////////////////////
        long [][]dp1 = new long[arr1.length][sum+1];

        for (int i = 1; arr1[0] * i < sum+1; i++) {
            dp1[0][arr1[0] * i] = 1;
        }

        for (int i = 0; i < arr1.length; i++) {
            dp1[i][0] =1;
        }

        for (int i = 1; i < arr1.length; i++) {//券
            for (int j = 1; j < sum+1; j++) {//钱
                dp1[i][j] = dp1[i-1][j];//不用这个券
                dp1[i][j] += j-arr1[i]>=0?dp1[i][j-arr1[i]]:0;//在用这个券的基础上，再用一张
                dp1[i][j] = dp1[i][j]%1000000007;
            }
        }

        /////////用币的   dp1_i,j  【0.。。i】号硬币，搞定j元有多少种方式 //////////
        long [][]dp2 = new long[arr2.length][sum+1];
        if(arr2[0]<=sum)
            dp2[0][arr2[0]] = 1;


        for (int i = 0; i < arr2.length; i++) {
            dp2[i][0] =1;
        }

        for (int i = 1; i < arr2.length; i++) {
            for (int j = 1; j < sum+1; j++) {
                dp2[i][j] = dp2[i-1][j];//不用这个硬币
                dp2[i][j] += j-arr2[i]>=0?dp2[i-1][j-arr2[i]]:0;//在不用这个币的基础上，用一个
                dp2[i][j] = dp2[i][j]%1000000007;
            }
        }
        /////////////////////////////////////////答案//////////////

        long res=0;
        for (int i = 0; i < sum+1; i++) {//组合求答案
                res += dp1[arr1.length-1][i] * dp2[arr2.length-1][sum-i];
            res = res%1000000007;
        }
        System.out.println(res);
    }
}